package com.yuan.algorithms.算法导论_第一部分;

/**
 * @author YouYuan <br>
 *         E-mail:1265161633@qq.com <br>
 *         创建时间：2015年12月7日 下午4:22:47 <br>
 *         说明:
 */
public class 数组中第k大的数 {

	public static void main(String[] args) {
		double[] arr = { 123, 333, 878, 2, 8, 1, 3, 7, 10, 999 };
		double kNum = selectK(arr, arr.length, 3);
		System.out.println(kNum);
	}

	private static double selectK(double[] arr, int n, int k) {
		mergeSort(arr, 0, n - 1);
		return arr[k - 1];

	}

	private static void mergeSort(double[] arr, int low, int hight) {
		// 若low>=hight,则该子数组最多有一个元素，所以已经排好序
		if (low < hight) {
			// 分解待排序的n个元素的序列成各具n/2个元素的两个子序列
			mergeSort(arr, low, (low + hight) / 2);
			mergeSort(arr, (low + hight) / 2 + 1, hight);
			// 合并两个有序序列
			merge(arr, low, (low + hight) / 2, hight);
		}
	}

	/**
	 * 合并两个有序序列并代替当前的数组arr
	 * 
	 * @param arr
	 *            存储序列的数组
	 * @param low
	 *            第一个有序序列的起始下标
	 * @param mid
	 *            有序序列的分隔点
	 * @param hight
	 *            第二个有序序列的终点
	 */
	private static void merge(double[] arr, int low, int mid, int hight) {
		double[] t = new double[hight - low + 1];
		int s = low;// 已排序的前半部分的下标
		int e = mid + 1;// 已排序的后半部分的下标
		int current = 0;
		while (s <= mid && e <= hight) {// 排序的范围
			if (arr[s] < arr[e]) {// 将较小的值存储到临时数组中，继续排列下一个值
				t[current++] = arr[s++];
			} else {
				t[current++] = arr[e++];
			}
		}
		// 因为已经是有序序列，可以将剩余的值直接存储到临时数组中
		while (s <= mid) {
			t[current++] = arr[s++];
		}
		while (e <= hight) {
			t[current++] = arr[e++];
		}
		// 将新的有序序列存储到原数组中
		for (int i = 0, len = t.length; i < len; i++) {
			arr[low + i] = t[i];
		}
	}

}
